package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何从无序链表中移除重复项

func main() {
	head := &common.LNode{}
	common.CreateNode2(head)

	fmt.Println("删除重复节点前：", head)

	//removeDup(head)
	removeDupRecursion(head)

	fmt.Println("删除重复节点后：", head)
}

// 方法一：顺序删除 时间复杂度 O(n^2) 空间复杂度 O(1)
func removeDup(head *common.LNode) {
	if head == nil || head.Next == nil {
		return
	}

	outerCurrent := head.Next
	var innerCurrent, innerPrevious *common.LNode

	for ; outerCurrent != nil; outerCurrent = outerCurrent.Next {
		for innerPrevious, innerCurrent = outerCurrent, outerCurrent.Next; innerCurrent != nil; {
			if outerCurrent.Data == innerCurrent.Data {
				innerPrevious.Next = innerCurrent.Next
			} else {
				innerPrevious = innerCurrent
			}
			innerCurrent = innerCurrent.Next
		}
	}
}

// 方法二：递归法
func removeDupRecursion(head *common.LNode) {
	if head == nil {
		return
	}

	head.Next = removeDupRecursionChild(head.Next)
}

func removeDupRecursionChild(head *common.LNode) *common.LNode {
	if head == nil || head.Next == nil {
		return head
	}

	head.Next = removeDupRecursionChild(head.Next)

	current := head
	next := head.Next

	for next != nil {
		if head.Data == next.Data {
			current.Next = next.Next
		} else {
			current = current.Next
		}
		next = current.Next
	}

	return head
}
